package com.future.offer;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Description: ��ָ Offer 38. �ַ���������
 * ����һ���ַ�������ӡ�����ַ������ַ����������С�
 * �����������˳�򷵻�����ַ������飬�����治�����ظ�Ԫ�ء�
 *
 * @author weiruibai.vendor
 * Date: 2022/5/26 10:42
 */
public class Solution_38 {

    public static void main(String[] args) {
        String s = "abc";
        System.out.println(permutation(s));
    }

    public static String[] permutation(String s) {
        List<Character> list = new ArrayList<>();
        for (Character ch : s.toCharArray()) {
            list.add(ch);
        }

        Set<String> ans = new HashSet<>();
        process(list, "", ans);
        String[] res = new String[ans.size()];
        int i = 0;
        for (String ss : ans) {
            res[i++] = ss;
        }
        return res;
    }

    private static void process(List<Character> list, String path, Set<String> ans) {
        if (list.size() == 0) {
            ans.add(path);
            return;
        }
        int N = list.size();
        for (int i = 0; i < N; i++) {
            char ch = list.get(i);
            list.remove(i);
            process(list, path + ch, ans);
            list.add(i, ch);
        }
    }
}
